package fun.ticsmyc.math;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * leetcode 89
 * @author Ticsmyc
 * @date 2021-03-22 10:47
 */
public class 格雷码 {

    /**
     关键是搞清楚格雷编码的生成过程, G(i) = i ^ (i/2);
     如 n = 3:
     G(0) = 000,
     G(1) = 1 ^ 0 = 001 ^ 000 = 001
     G(2) = 2 ^ 1 = 010 ^ 001 = 011
     G(3) = 3 ^ 1 = 011 ^ 001 = 010
     G(4) = 4 ^ 2 = 100 ^ 010 = 110
     G(5) = 5 ^ 2 = 101 ^ 010 = 111
     G(6) = 6 ^ 3 = 110 ^ 011 = 101
     G(7) = 7 ^ 3 = 111 ^ 011 = 100
     **/
    public List<Integer> grayCode(int n) {
        List<Integer> ret = new ArrayList<>();
        for(int i = 0; i < 1<<n; ++i)
            ret.add(i ^ i>>1);
        return ret;
    }


    /**
     * 对称构造
     * G(n)是在G(n-1)所有数前面添个1
     *  00  01
     *  0   1
     *  00  01   11  10
     *   0   1    3   2
     *  000  001  011  010  110 111  101  100
     *   0    1    3    2    6   7    5    4
     * @param n
     * @return
     */
    public List<Integer> grayCode2(int n){
        List<Integer> res = new ArrayList<>();
        res.add(0);
        for(int i=0;i<n;++i){
            for(int j=res.size()-1;j>=0;--j){
                res.add(res.get(j)+(int)Math.pow(2,i));
            }
        }
        return res;
    }

    @Test
    public void test(){
        List<Integer> integers = grayCode2(3);
        for (int i = 0; i < integers.size(); i++) {
            System.out.print(integers.get(i)+"\t");
        }
    }

}
